package top.humbleyuan.stack;

import top.humbleyuan.datastructure.linkedlist.LinkNode;
import top.humbleyuan.datastructure.linkedlist.MyEntry;

import java.util.Arrays;
import java.util.Stack;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 22:48
 * @Des 链表中下一个更大节点
 */
public class LeetCode_1019 {
    public static void main(String[] args) {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(2);
        int[] vals = {1,5};
        head = LinkNode.formLink(head,vals);

        Stack<MyEntry<Integer,Integer>> stack = new Stack<>();
        int[] largerArray = new int[10000];

        LinkNode temp = head;
        int length = 0;

        while (temp != null) {
            if(!stack.empty() && temp.val > stack.peek().getValue()) {
                largerArray[stack.peek().getKey()] = temp.val;
                stack.pop();
                continue;
            }
            stack.push(new MyEntry<>(length,temp.val));
            temp = temp.next;
            length ++;
        }

        Arrays.copyOfRange(largerArray,0,length);
    }


    // 用数组代替MyEntry
    public static void m2() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(2);
        int[] vals = {7,4,3,5};
        head = LinkNode.formLink(head,vals);

        Stack<Integer> stack = new Stack<>();
        int[] largerArray = new int[10000];
        int[] arr1 = new int[10000];

        LinkNode temp = head;
        int length = 0;

        while (temp != null) {
            if(!stack.empty() && temp.val > stack.peek()) {
                largerArray[arr1[stack.size() - 1]] = temp.val;
                stack.pop();
                continue;
            }

            stack.push(temp.val);
            arr1[stack.size() - 1] = length;

            temp = temp.next;
            length ++;
        }

        Arrays.copyOfRange(largerArray,0,length);
    }

    //用动态变动数组代替栈，效率要高(别人)
    public static void m3() {
        /**
         * 数据准备
         */
        LinkNode head = new LinkNode(2);
        int[] vals = {1,5};
        head = LinkNode.formLink(head,vals);

        int[] stack = new int[10000];
        int[] res = new int[10000];
        int[] temp = new int[10000];
        int top = -1, i = 0;
        LinkNode node = head;

        while (node != null) {
            while (top != -1 && temp[stack[top]] < node.val)
                res[stack[top--]] = node.val;
            stack[++top] = i;
            temp[i++] = node.val;
            node = node.next;
        }
        Arrays.copyOf(res, i);
    }
}
